package com.dmall.chapter09.section03;

import com.dmall.chapter02.section09.Graph;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 哈密尔顿回路算法
 * @author wx
 * @date 2020-03-16 09:05:58
 */
public class HamiltonLoop1 {

    private Graph G;
    private boolean[] visited;
    private int[] pre;
    private int end;

    public HamiltonLoop1(Graph G) {
        this.G = G;
        this.visited = new boolean[G.V()];
        this.pre = new int[G.V()];
        this.end = -1;
        dfs(0, 0);
    }

    private boolean dfs(int v, int parent) {
        visited[v] = true;
        pre[v] = parent;
        for (int w : G.adj(v)) {
            if (!visited[w]) {
                if (dfs(w, v)) {
                    return true;
                }
            } else if (w == 0 && allVisited()) {
                end = v;
                return true;
            }
        }
        visited[v] = false;
        // 在这里并不需要为pre[v]赋值，因为重新回溯之后会为pre[v]赋值
        return false;
    }

    private boolean allVisited() {
        for (int i = 0; i < G.V(); i++) {
            if (!visited[i]) {
                return false;
            }
        }
        return true;
    }

    public List<Integer> result() {
        List<Integer> res = new ArrayList<>();
        if (end == -1) {
            return res;
        }
        int cur = end;
        while (cur != 0) {
            res.add(cur);
            cur = pre[cur];
        }
        res.add(0);
        Collections.reverse(res);
        return res;
    }

    public static void main(String[] args) {
        String filename = HamiltonLoop1.class.getClassLoader().getResource("g.txt").getPath();
        Graph g = new Graph(filename);
        HamiltonLoop1 hl = new HamiltonLoop1(g);
        System.out.println(hl.result());

        String filename2 = HamiltonLoop1.class.getClassLoader().getResource("g2.txt").getPath();
        Graph g2 = new Graph(filename2);
        HamiltonLoop1 hl2 = new HamiltonLoop1(g2);
        System.out.println(hl2.result());
    }
}
